import java.util.*;
/**
 * 链表排序
 * 使用归并排序算法对链表进行排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(logn)，递归调用栈的深度
 */
public class sortList {
    /**
     * 链表节点类
     * 包含节点值和指向下一个节点的引用
     */
    public static class ListNode{
        int val;        // 节点值
        ListNode next;  // 指向下一个节点的引用
        ListNode(int val){
            this.val = val;
        }
    }

    /**
     * 链表排序的主方法
     * 使用归并排序算法：
     * 1. 找到链表的中点
     * 2. 将链表分成两半
     * 3. 递归排序两半
     * 4. 合并两个有序链表
     * @param head 链表头节点
     * @return 排序后的链表头节点
     */
    public static ListNode sortListM(ListNode head){
        // 递归终止条件：链表为空或只有一个节点
        if(head == null || head.next == null){
            return head;
        }
        // 找到链表的中点
        ListNode mid = findMid(head);
        // 将链表分成两半
        ListNode leftHead = head;
        ListNode rightHead = mid.next;
        mid.next = null;  // 断开链表

        // 递归排序两半
        ListNode left = sortListM(leftHead);
        ListNode right = sortListM(rightHead);

        // 合并两个有序链表
        return merge2Lists(left, right);
    }

    /**
     * 使用快慢指针找到链表的中点
     * 快指针每次移动两步，慢指针每次移动一步
     * 当快指针到达链表末尾时，慢指针指向中点
     * @param head 链表头节点
     * @return 链表的中点节点
     */
    public static ListNode findMid(ListNode head){
        // fast 从 head.next 开始，确保 slow 指向中点或左中点
        ListNode fast = head.next;  // 快指针从第二个节点开始
        ListNode slow = head;       // 慢指针从第一个节点开始
        while(fast != null && fast.next != null){
            fast = fast.next.next;  // 快指针移动两步
            slow = slow.next;       // 慢指针移动一步
        }
        return slow;
    }

    /**
     * 合并两个有序链表
     * @param l1 第一个有序链表
     * @param l2 第二个有序链表
     * @return 合并后的有序链表
     */
    public static ListNode merge2Lists(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);  // 虚拟头节点
        ListNode now = dummy;
        // 比较两个链表的节点值，将较小的节点连接到结果链表
        while(l1 != null && l2 != null){
            if(l1.val > l2.val){
                now.next = l2;
                l2 = l2.next;
                now = now.next;
            }else{
                now.next = l1;
                l1 = l1.next;
                now = now.next;
            }
        }
        // 处理剩余节点
        if(l1 != null) now.next = l1;
        if(l2 != null) now.next = l2;
        return dummy.next;
    }

    //-----------------------------------------------------------------------------------------------
    /**
     * 简单的链表排序方法
     * 将链表转换为数组，排序后再转回链表
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(n)
     */
    public ListNode simple(ListNode head) {
        // 将链表转换为数组
        List<Integer> list = new ArrayList<>();
        ListNode l = head;
        while(l != null){
            list.add(l.val);
            l = l.next;
        }
        Integer[] nums = list.toArray(new Integer[0]);
        // Arrays.sort(nums);  // 使用Java内置排序
        quickSort(nums, 0, nums.length - 1);  // 使用快速排序
        
        // 将排序后的数组转回链表
        l = head;
        for(int i = 0; i < nums.length; i++){
            l.val = nums[i];
            l = l.next;
        }
        return head;
    }

    /**
     * 快速排序算法
     * @param nums 待排序数组
     * @param left 左边界
     * @param right 右边界
     */
    public void quickSort(Integer[] nums, int left, int right){
        if(left < right){
            int pivotIndex = partition(nums, left, right);
            quickSort(nums, left, pivotIndex);
            quickSort(nums, pivotIndex + 1, right);
        }
    }

    /**
     * 快速排序的分区操作
     * @param nums 待分区数组
     * @param left 左边界
     * @param right 右边界
     * @return 基准元素的位置
     */
    public int partition(Integer[] nums, int left, int right){
        int pivot = nums[left];  // 选择第一个元素作为基准
        while(left < right){
            // 从右边开始找小于基准的元素
            while(left < right && nums[right] >= pivot) right--;
            nums[left] = nums[right];
            // 从左边开始找大于基准的元素
            while(left < right && nums[left] <= pivot) left++;
            nums[right] = nums[left];
        }
        nums[left] = pivot;  // 将基准元素放到正确的位置
        return left;
    }
    //-----------------------------------------------------------------------------------------------

    /**
     * 主函数：处理输入输出
     * 从控制台读取链表节点值，排序后输出
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 读取链表节点值
        String[] s = sc.nextLine().split(" ");
        // 创建链表
        ListNode dummy = new ListNode(0);
        ListNode now = dummy;
        for(int i = 0; i < s.length; i++){
            now.next = new ListNode(Integer.parseInt(s[i]));
            now = now.next;
        }
        // 排序并输出结果
        ListNode result = sortListM(dummy.next);
        while(result != null){
            System.out.print(result.val + " ");
            result = result.next;
        }
        sc.close();
    }
}
